/*
Date:20210608 23:24PM
key:01背包中 dp[i][j]的j未必是物品体积容量，还有可能是价值容量。
    首先这题也是自由分配+ -号(具体解释看题解)，因此当+号集合越接近sum/2时，结果越好，因此求价值容量为sum/2 +1下的最大值
*/
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) 
    {
        if(stones.size()==1){return stones[0];}
        const int n=stones.size();
        //比如23，应该是11.5向上取整为价值容量上限。
        const int m=(accumulate(stones.begin(),stones.end(),0)>>1)+1;
        cout<<m;
        int**dp=new int*[n+1];
        for(int i=0;i<n+1;i++)
        {
            dp[i]=new int[m+1];
        }
        for(int i=1;i<m+1;i++)
        {
            dp[0][i]=0;
        }
        dp[0][0]=1;
        for(int i=1;i<n+1;i++)
        {
            for(int j=0;j<m+1;j++)
            {
                //选第i个
                if(j-stones[i-1]>0)
                {
                    if(stones[i-1]+dp[i-1][j-stones[i-1]]<m+1)
                    {
                        dp[i][j]=max(dp[i-1][j],stones[i-1]+dp[i-1][j-stones[i-1]]);
                        continue;
                    }
                }
                dp[i][j]=dp[i-1][j];
            }
        }
        return accumulate(stones.begin(),stones.end(),0)-2*dp[n][m];
    }
};